package 热题100.贪心.划分字母区间_763_中等;

import java.util.ArrayList;
import java.util.List;

/*
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：
输入：s = "eccbbbbdec"
输出：[10]

提示：
1 <= s.length <= 500
s 仅由小写英文字母组成

思路：
    找到每一个字母的边界，如果找到之前遍历过所有字母的最远边界，就是分割点。
    1. 遍历一遍记录每个字母的最远位置
    2. 遍历第二遍，更新记录所遍历字母出现最远边界的值，当遍历到该下标后，就是分割点。
    因为一串字符假如某个字母的最远边界是8，当遍历到8之前，这段区间的最远边界还没更新
    导致最远边界和遍历的下标一样，说明此时就是一个分割点。如果不是分割点，说明后面还
    会出现这一段字符的字母，那么某个字母的最远边界会>8，但是8并未被更新，所以这个点一定是分割点。

* */
public class Solution {
    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        List<Integer> ans = partitionLabels(s);
        for (int t : ans){
            System.out.println(t);
        }
    }

    public static List<Integer> partitionLabels(String s) {
        List<Integer> ans = new ArrayList<>();
        char[] strs = s.toCharArray();
        int[] hash = new int[26];
        for (int i = 0; i < strs.length; i ++){
            hash[strs[i] - 'a'] = i;
        }
        int maxLen = 0;
        int last = -1;
        for (int i = 0; i < strs.length; i ++){
            maxLen = Math.max(hash[strs[i] - 'a'], maxLen);
            if (maxLen == i){
                // 记录上一个的最大值，因为答案要求的是每一个片段的长度，初始等于-1，相当于i + 1了，即将下标转换为了长度
                ans.add(i  - last);
                last = i;
            }
        }
        return ans;
    }
}
